package william.xor;

/**
 * @author ZhangShenao
 * @date 2024/1/19
 * @description <a href="https://leetcode.cn/problems/single-number-ii/description/">...</a>
 */
public class Leetcode137_只出现一次的数字2 {
    /**
     * 采用Bit Map的思想
     * Step1: 使用一个长度为32的long[]数组states,记录所有元素在该位的状态和。如states[5]即所有元素在第5位的状态和。
     * Step2: 将数组中的每个元素,按照二进制形式,将每一位的状态相加到states数组中。
     * Step3: 遍历states数组,如果某位上的元素%3!=0,说明目标数字在该位为1,保存在结果中。
     * Step4: states数组遍历完成,返回最终结果。
     */
    public int singleNumber(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            throw new IllegalArgumentException("iiegal input!!");
        }

        //使用一个32位的long数组,保存所有元素的状态和
        long[] states = new long[32];

        //遍历所有元素,以二进制的形式,将状态和保存到states数组中
        for (int n : nums) {
            for (int i = 0; i < 32; i++) {
                states[i] += ((n >> i) & 1);
            }
        }

        //遍历状态数组,判断每一位的元素,如果%3 != 0,说明目标数字在该位上一定为1,保存结果
        int answer = 0;
        for (int i = 0; i < states.length; i++) {
            if (states[i] % 3 != 0) {
                answer |= (1 << i);
            }
        }

        //返回最终结果
        return answer;

    }
}
